
/*-------------------------------------------------------------------------
 *
 * tidbitmap.c
 *	  PostgreSQL 元组标识符 (TID) 位图包
 *
 * 本模块提供的数据结构与 Bitmapsets 在精神上类似，但特别
 * 适应于存储元组标识符 (TIDs) 或 ItemPointers 的集合。具体而言， 
 * ItemPointer 分为 BlockNumber 和 OffsetNumber 的划分被考虑在内。
 * 此外，由于我们希望能够在内存中存储非常大的元组集合，因此
 * 我们支持“有损”存储，在这种存储中，我们不再记住页面上个
 * 别元组的偏移量，而只记住某个特定页面需要被访问的事实。
 *
 * “有损”存储每个磁盘页面使用一个比特，因此在标准的 8K 
 * BLCKSZ 下，我们可以在大约 1Mb 的内存中代表 64Gb 磁盘空间
 * 中的所有页面。处理如此大小的表的人应该有几个 Mb 的剩余
 * 空间，因此我们不担心提供第二级的有损存储。在理论上，我们
 * 可以在某些时候退回到页面范围，但目前看起来这是无益的复杂
 * 性。
 *
 * 我们还支持候选匹配或重复检查的概念。这意味着我们知道搜索
 * 只需访问页面上的某些元组，但我们不确定这些元组是否都是实
 * 际匹配。因此，最终的堆扫描必须仅重新检查这些元组的条件，
 * 而不是像有损位图情况下那样重新检查页面上所有元组的条件。
 * 在将 TIDs 插入位图时，可以特别指定重新检查，并且在我们对
 * 一个有损分页和一个非有损页面进行 AND 操作时，也可以内部
 * 发生重新检查。
 *
 *
 * Copyright (c) 2003-2022, PostgreSQL Global Development Group
 *
 * IDENTIFICATION
 *	  src/backend/nodes/tidbitmap.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include <limits.h>

#include "access/htup_details.h"
#include "common/hashfn.h"
#include "nodes/bitmapset.h"
#include "nodes/tidbitmap.h"
#include "storage/lwlock.h"
#include "utils/dsa.h"

/*
 * 每页的最大元组数不大（通常 256 个 8K 页，或 1024 个 32K 页）。因此，制作
 * 每页位图的可变大小没有太大意义。我们只是规定大小 
 * 是这样的：
 */
#define MAX_TUPLES_PER_PAGE  MaxHeapTuplesPerPage

/*
 * 当我们必须切换到有损存储时，我们使用一个数据结构
 * 每页一个比特，其中所有页面具有相同的编号 DIV
 * PAGES_PER_CHUNK 被聚合成一个块。当一个块存在
 * 并且为给定页面设置了比特时，页面表中不能有该页面的逐页条目。
 *
 * 我们实际上在同一个哈希表中存储精确页面和有损块，
 * 使用相同的数据结构。（这是因为哈希表的内存
 * 管理不容易/有效地允许空间从一个哈希表轻松转移到另一个哈希表。）因此，最好
 * 如果 PAGES_PER_CHUNK 与 MAX_TUPLES_PER_PAGE 相同，或者至少
 * 不太不同。但我们也希望 PAGES_PER_CHUNK 是 2 的幂以
 * 避免高成本的整数余数操作。所以，像这样定义它：
 */
#define PAGES_PER_CHUNK  (BLCKSZ / 32)

/* 我们使用 BITS_PER_BITMAPWORD 并从 nodes/bitmapset.h 类型定义 bitmapword */

#define WORDNUM(x)	((x) / BITS_PER_BITMAPWORD)
#define BITNUM(x)	((x) % BITS_PER_BITMAPWORD)

/* 精确页面的活动字数： */
#define WORDS_PER_PAGE	((MAX_TUPLES_PER_PAGE - 1) / BITS_PER_BITMAPWORD + 1)
/* 有损块的活动字数： */
#define WORDS_PER_CHUNK  ((PAGES_PER_CHUNK - 1) / BITS_PER_BITMAPWORD + 1)

/*
 * 哈希表条目由这个数据结构表示。对于
 * 精确页面，blockno 是页面号码，位 k 的位图
 * 代表元组偏移量 k+1。对于损失块，blockno 是块中的第一个
 * 页面（这必须是 PAGES_PER_CHUNK 的倍数），而位 k 表示页面 blockno+k。
 * 请注意，如果我们对块范围内的任何页面使用
 * 损失存储，则无法对块的第一个页面进行精确存储，因为同一个
 * 哈希表条目必须兼顾这两种目的。
 *
 * recheck 仅用于精确页面 --- 它表示尽管
 * 只需要检查所述元组，但必须检查每个的完整索引条件
 * （即，这些是候选匹配）。
 */
typedef struct PagetableEntry
{
	BlockNumber blockno;		/* 页面号码（哈希表键） */
	char		status;			/* 哈希条目状态 */
	bool		ischunk;		/* T = 损失存储，F = 精确 */
	bool		recheck;		/* 元组是否需要重新检查？ */
	bitmapword	words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)];
} PagetableEntry;

/*
 * 保存页表条目的数组。
 */
typedef struct PTEntryArray
{
	pg_atomic_uint32 refcount;	/* 附加的迭代器数量 */
	PagetableEntry ptentry[FLEXIBLE_ARRAY_MEMBER];
} PTEntryArray;

/*
 * 我们想要避免创建哈希表的开销，
 * 这是相对较大的，当没有必要时。特别是在我们使用
 * 嵌套循环连接的内部进行位图扫描时：在这种情况下，位图可能只
 * 存活足够长的时间累积一个条目。因此，我们避免
 * 在需要两个页表条目之前创建实际的哈希表。
 * 当只需要一个页表条目时，我们将其存储在一个固定的字段中
 * TIDBitMap。（注意：如果位图后来缩减到零或一个页面，我们不会
 * 取消哈希表的创建。因此，当 nentries 为零或一时，状态可以是 TBM_HASH。）
 */
typedef enum
{
	TBM_EMPTY,					/* 无哈希表，nentries == 0 */
	TBM_ONE_PAGE,				/* entry1 包含单个条目 */
	TBM_HASH					/* 页表有效，entry1 无效 */
} TBMStatus;

/*
 * TBM 的当前迭代状态。
 */
typedef enum
{
	TBM_NOT_ITERATING,			/* 尚未转换为页面和块数组 */
	TBM_ITERATING_PRIVATE,		/* 转换为本地页面和块数组 */
	TBM_ITERATING_SHARED		/* 转换为共享页面和块数组 */
} TBMIteratingState;

/*
 * 这里是整个 TIDBitMap 的表示：
 */
struct TIDBitmap
{
	NodeTag		type;			/* 使其成为有效的节点 */
	MemoryContext mcxt;			/* 包含我的内存上下文 */
	TBMStatus	status;			/* 参见上面的代码 */
	struct pagetable_hash *pagetable;	/* 页表条目的哈希表 */
	int			nentries;		/* 页表中的条目数量 */
	int			maxentries;		/* 限制以符合 maxbytes */
	int			npages;			/* 页表中的精确条目数量 */
	int			nchunks;		/* 页表中的损失条目数量 */
	TBMIteratingState iterating;	/* 是否调用了 tbm_begin_iterate？ */
	uint32		lossify_start;	/* 用于开始损失哈希表的偏移量 */
	PagetableEntry entry1;		/* 当状态 == TBM_ONE_PAGE 时使用 */
	/* 当迭代为真时有效： */
	PagetableEntry **spages;	/* 排序的精确页面列表，或 NULL */
	PagetableEntry **schunks;	/* 排序的损失块列表，或 NULL */
	dsa_pointer dsapagetable;	/* dsa_pointer 指向元素数组 */
	dsa_pointer dsapagetableold;	/* dsa_pointer 指向旧元素数组 */
	dsa_pointer ptpages;		/* dsa_pointer 指向页面数组 */
	dsa_pointer ptchunks;		/* dsa_pointer 指向块数组 */
	dsa_area   *dsa;			/* 针对每个查询的 dsa 区域的引用 */
};

/*
 * 在按排序顺序遍历位图时，使用 TBMIterator 来跟踪我们的进度。
 * 可以有多个迭代器同时扫描同一位图。请注意，一旦创建任何迭代器，
 * 位图变为只读。
 */
struct TBMIterator
{
	TIDBitmap  *tbm;			/* 我们正在遍历的 TIDBitmap */
	int			spageptr;		/* 下一个 spages 索引 */
	int			schunkptr;		/* 下一个 schunks 索引 */
	int			schunkbit;		/* 当前 schunk 中要检查的下一个位 */
	TBMIterateResult output;	/* 必须是最后一个（因为大小可变） */
};

/*
 * 保持迭代器的共享成员，以便多个进程可以共同迭代。
 */
typedef struct TBMSharedIteratorState
{
	int			nentries;		/* 页表中的条目数量 */
	int			maxentries;		/* 限制以符合 maxbytes */
	int			npages;			/* 页表中的精确条目数量 */
	int			nchunks;		/* 页表中的损失条目数量 */
	dsa_pointer pagetable;		/* dsa 指针指向页表数据的头部 */
	dsa_pointer spages;			/* dsa 指针指向页面数组 */
	dsa_pointer schunks;		/* dsa 指针指向块数组 */
	LWLock		lock;			/* 保护下面成员的锁 */
	int			spageptr;		/* 下一个 spages 索引 */
	int			schunkptr;		/* 下一个 schunks 索引 */
	int			schunkbit;		/* 当前 schunk 中要检查的下一个位 */
} TBMSharedIteratorState;

/*
 * 页表迭代数组。
 */
typedef struct PTIterationArray
{
	pg_atomic_uint32 refcount;	/* 附加的迭代器数量 */
	int			index[FLEXIBLE_ARRAY_MEMBER];	/* 索引数组 */
} PTIterationArray;

/*
 * 与 TBMIterator 相同，但用于联合迭代，因此它
 * 还持有对共享状态的引用。
 */
struct TBMSharedIterator
{
	TBMSharedIteratorState *state;	/* 共享状态 */
	PTEntryArray *ptbase;		/* 页表元素数组 */
	PTIterationArray *ptpages;	/* 排序的精确页面索引列表 */
	PTIterationArray *ptchunks; /* 排序的有损页面索引列表 */
	TBMIterateResult output;	/* 必须是最后一个（因为大小可变） */
};

/* 本地函数原型 */
static void fc_tbm_union_page(TIDBitmap *fc_a, const PagetableEntry *fc_bpage);
static bool fc_tbm_intersect_page(TIDBitmap *fc_a, PagetableEntry *fc_apage,
							   const TIDBitmap *fc_b);
static const PagetableEntry *fc_tbm_find_pageentry(const TIDBitmap *fc_tbm,
												BlockNumber fc_pageno);
static PagetableEntry *fc_tbm_get_pageentry(TIDBitmap *fc_tbm, BlockNumber fc_pageno);
static bool fc_tbm_page_is_lossy(const TIDBitmap *fc_tbm, BlockNumber fc_pageno);
static void fc_tbm_mark_page_lossy(TIDBitmap *fc_tbm, BlockNumber fc_pageno);
static void fc_tbm_lossify(TIDBitmap *fc_tbm);
static int	fc_tbm_comparator(const void *fc_left, const void *fc_right);
static int	fc_tbm_shared_comparator(const void *fc_left, const void *fc_right,
								  void *fc_arg);

/* 定义哈希表将块编号映射到 PagetableEntry */
#define SH_USE_NONDEFAULT_ALLOCATOR
#define SH_PREFIX pagetable
#define SH_ELEMENT_TYPE PagetableEntry
#define SH_KEY_TYPE BlockNumber
#define SH_KEY blockno
#define SH_HASH_KEY(tb, key) murmurhash32(key)
#define SH_EQUAL(tb, a, b) a == b
#define SH_SCOPE static inline
#define SH_DEFINE
#define SH_DECLARE
#include "lib/simplehash.h"


/*
 * tbm_create - 创建一个初始为空的位图
 *
 * 位图将存在于此调用时的 CurrentMemoryContext 的内存上下文中。
 * 它的总内存消耗将限制为（大约）maxbytes。
 * 如果传递给此函数的 DSA 不是 NULL，
 * 则用于存储底层页表元素的内存将从 DSA 中分配。
 */
TIDBitmap *
tbm_create(long fc_maxbytes, dsa_area *fc_dsa)
{
	TIDBitmap  *fc_tbm;

	/* 创建 TIDBitmap 结构并将所有字段置为零 */
	fc_tbm = makeNode(TIDBitmap);

	fc_tbm->mcxt = CurrentMemoryContext;
	fc_tbm->status = TBM_EMPTY;

	fc_tbm->maxentries = (int) tbm_calculate_entries(fc_maxbytes);
	fc_tbm->lossify_start = 0;
	fc_tbm->dsa = fc_dsa;
	fc_tbm->dsapagetable = InvalidDsaPointer;
	fc_tbm->dsapagetableold = InvalidDsaPointer;
	fc_tbm->ptpages = InvalidDsaPointer;
	fc_tbm->ptchunks = InvalidDsaPointer;

	return fc_tbm;
}

/*
 * 实际创建哈希表。由于这是一个适度昂贵的
 * 提议，我们不在必须时才执行此操作。
 */
static void fc_tbm_create_pagetable(TIDBitmap *fc_tbm)
{
	Assert(fc_tbm->status != TBM_HASH);
	Assert(fc_tbm->pagetable == NULL);

	fc_tbm->pagetable = pagetable_create(fc_tbm->mcxt, 128, fc_tbm);

	/* 如果 entry1 有效，则将其推入哈希表 */
	if (fc_tbm->status == TBM_ONE_PAGE)
	{
		PagetableEntry *fc_page;
		bool		fc_found;
		char		fc_oldstatus;

		fc_page = pagetable_insert(fc_tbm->pagetable,
								fc_tbm->entry1.blockno,
								&fc_found);
		Assert(!fc_found);
		fc_oldstatus = fc_page->status;
		memcpy(fc_page, &fc_tbm->entry1, sizeof(PagetableEntry));
		fc_page->status = fc_oldstatus;
	}

	fc_tbm->status = TBM_HASH;
}

/*
 * tbm_free - 释放 TIDBitmap
 */
void tbm_free(TIDBitmap *fc_tbm)
{
	if (fc_tbm->pagetable)
		pagetable_destroy(fc_tbm->pagetable);
	if (fc_tbm->spages)
		pfree(fc_tbm->spages);
	if (fc_tbm->schunks)
		pfree(fc_tbm->schunks);
	pfree(fc_tbm);
}

/*
 * tbm_free_shared_area - 释放共享状态
 *
 * 释放共享迭代器状态，如果它们不被任何共享迭代器引用
 * 例如，如果 recount 变为 0，也释放共享页表和迭代器数组的内存。
 */
void tbm_free_shared_area(dsa_area *fc_dsa, dsa_pointer fc_dp)
{
	TBMSharedIteratorState *fc_istate = dsa_get_address(fc_dsa, fc_dp);
	PTEntryArray *fc_ptbase;
	PTIterationArray *fc_ptpages;
	PTIterationArray *fc_ptchunks;

	if (DsaPointerIsValid(fc_istate->pagetable))
	{
		fc_ptbase = dsa_get_address(fc_dsa, fc_istate->pagetable);
		if (pg_atomic_sub_fetch_u32(&fc_ptbase->refcount, 1) == 0)
			dsa_free(fc_dsa, fc_istate->pagetable);
	}
	if (DsaPointerIsValid(fc_istate->spages))
	{
		fc_ptpages = dsa_get_address(fc_dsa, fc_istate->spages);
		if (pg_atomic_sub_fetch_u32(&fc_ptpages->refcount, 1) == 0)
			dsa_free(fc_dsa, fc_istate->spages);
	}
	if (DsaPointerIsValid(fc_istate->schunks))
	{
		fc_ptchunks = dsa_get_address(fc_dsa, fc_istate->schunks);
		if (pg_atomic_sub_fetch_u32(&fc_ptchunks->refcount, 1) == 0)
			dsa_free(fc_dsa, fc_istate->schunks);
	}

	dsa_free(fc_dsa, fc_dp);
}

/*
 * tbm_add_tuples - 向 TIDBitmap 添加一些元组 ID
 *
 * 如果 recheck 为真，当报告这些元组时
 * TBMIterateResult 中将设置重新检查标志。
 */
void tbm_add_tuples(TIDBitmap *fc_tbm, const ItemPointer fc_tids, int fc_ntids,
			   bool fc_recheck)
{
	BlockNumber fc_currblk = InvalidBlockNumber;
	PagetableEntry *fc_page = NULL;	/* 仅在 currblk 有效时有效 */
	int			fc_i;

	Assert(fc_tbm->iterating == TBM_NOT_ITERATING);
	for (fc_i = 0; fc_i < fc_ntids; fc_i++)
	{
		BlockNumber fc_blk = ItemPointerGetBlockNumber(fc_tids + fc_i);
		OffsetNumber fc_off = ItemPointerGetOffsetNumber(fc_tids + fc_i);
		int			fc_wordnum,
					fc_bitnum;

		/* 安全检查以确保我们不超过位数组边界 */
		if (fc_off < 1 || fc_off > MAX_TUPLES_PER_PAGE)
			elog(ERROR, "tuple offset out of range: %u", fc_off);

		/*
		 * 除非我们已经查找过目标页面，否则查找目标页面。
		 * 当输入包含同一页面上的连续元组时，这可以节省周期，
		 * 这种情况足够常见，因此这里的额外测试是合理的。
		 */
		if (fc_blk != fc_currblk)
		{
			if (fc_tbm_page_is_lossy(fc_tbm, fc_blk))
				fc_page = NULL;	/* 牢记页面是损失的 */
			else
				fc_page = fc_tbm_get_pageentry(fc_tbm, fc_blk);
			fc_currblk = fc_blk;
		}

		if (fc_page == NULL)
			continue;			/* 整个页面已经标记 */

		if (fc_page->ischunk)
		{
			/* 该页面是损失块头，设置自身位 */
			fc_wordnum = fc_bitnum = 0;
		}
		else
		{
			/* 页面是精确的，因此为单个元组设置位 */
			fc_wordnum = WORDNUM(fc_off - 1);
			fc_bitnum = BITNUM(fc_off - 1);
		}
		fc_page->words[fc_wordnum] |= ((bitmapword) 1 << fc_bitnum);
		fc_page->recheck |= fc_recheck;

		if (fc_tbm->nentries > fc_tbm->maxentries)
		{
			fc_tbm_lossify(fc_tbm);
			/* 页面可能已经转换为损失，因此强制新查找 */
			fc_currblk = InvalidBlockNumber;
		}
	}
}

/*
 * tbm_add_page - 向 TIDBitmap 添加整个页面
 *
 * 这会导致整个页面在扫描 TIDBitmap 时被报告（带有重新检查标志）。
 */
void tbm_add_page(TIDBitmap *fc_tbm, BlockNumber fc_pageno)
{
	/* 在位图中输入页面，或如果已存在则标记为损失 */
	fc_tbm_mark_page_lossy(fc_tbm, fc_pageno);
	/* 如果我们超过了内存限制，则再损失一些页面 */
	if (fc_tbm->nentries > fc_tbm->maxentries)
		fc_tbm_lossify(fc_tbm);
}

/*
 * tbm_union - 设置并集
 *
 * a 被就地修改，b 未被更改
 */
void tbm_union(TIDBitmap *fc_a, const TIDBitmap *fc_b)
{
	Assert(!fc_a->iterating);
	/* 如果 b 为空则没有什么可做的 */
	if (fc_b->nentries == 0)
		return;
	/* 扫描 b 中的块和页面，将它们合并到 a 中 */
	if (fc_b->status == TBM_ONE_PAGE)
		fc_tbm_union_page(fc_a, &fc_b->entry1);
	else
	{
		pagetable_iterator fc_i;
		PagetableEntry *fc_bpage;

		Assert(fc_b->status == TBM_HASH);
		pagetable_start_iterate(fc_b->pagetable, &fc_i);
		while ((fc_bpage = pagetable_iterate(fc_b->pagetable, &fc_i)) != NULL)
			fc_tbm_union_page(fc_a, fc_bpage);
	}
}

/* 在并集操作期间处理 b 的一个页面 */
static void fc_tbm_union_page(TIDBitmap *fc_a, const PagetableEntry *fc_bpage)
{
	PagetableEntry *fc_apage;
	int			fc_wordnum;

	if (fc_bpage->ischunk)
	{
		/* 扫描 b 的块，在 a 中标记每个指示的页面为损失 */
		for (fc_wordnum = 0; fc_wordnum < WORDS_PER_CHUNK; fc_wordnum++)
		{
			bitmapword	fc_w = fc_bpage->words[fc_wordnum];

			if (fc_w != 0)
			{
				BlockNumber fc_pg;

				fc_pg = fc_bpage->blockno + (fc_wordnum * BITS_PER_BITMAPWORD);
				while (fc_w != 0)
				{
					if (fc_w & 1)
						fc_tbm_mark_page_lossy(fc_a, fc_pg);
					fc_pg++;
					fc_w >>= 1;
				}
			}
		}
	}
	else if (fc_tbm_page_is_lossy(fc_a, fc_bpage->blockno))
	{
		/* 页面在 a 中已经是损失的，没什么可做的 */
		return;
	}
	else
	{
		fc_apage = fc_tbm_get_pageentry(fc_a, fc_bpage->blockno);
		if (fc_apage->ischunk)
		{
			/* 该页面是损失块头，设置自身位 */
			fc_apage->words[0] |= ((bitmapword) 1 << 0);
		}
		else
		{
			/* 两个页面都是精确的，在位级别合并 */
			for (fc_wordnum = 0; fc_wordnum < WORDS_PER_PAGE; fc_wordnum++)
				fc_apage->words[fc_wordnum] |= fc_bpage->words[fc_wordnum];
			fc_apage->recheck |= fc_bpage->recheck;
		}
	}

	if (fc_a->nentries > fc_a->maxentries)
		fc_tbm_lossify(fc_a);
}

/*
 * tbm_intersect - 设置交集
 *
 * a 被就地修改，b 未被更改
 */
void tbm_intersect(TIDBitmap *fc_a, const TIDBitmap *fc_b)
{
	Assert(!fc_a->iterating);
	/* 如果 a 为空则没有什么可做的 */
	if (fc_a->nentries == 0)
		return;
	/* 扫描 a 中的块和页面，尝试与 b 匹配 */
	if (fc_a->status == TBM_ONE_PAGE)
	{
		if (fc_tbm_intersect_page(fc_a, &fc_a->entry1, fc_b))
		{
			/* 页面现在为空，从 a 中移除 */
			Assert(!fc_a->entry1.ischunk);
			fc_a->npages--;
			fc_a->nentries--;
			Assert(fc_a->nentries == 0);
			fc_a->status = TBM_EMPTY;
		}
	}
	else
	{
		pagetable_iterator fc_i;
		PagetableEntry *fc_apage;

		Assert(fc_a->status == TBM_HASH);
		pagetable_start_iterate(fc_a->pagetable, &fc_i);
		while ((fc_apage = pagetable_iterate(fc_a->pagetable, &fc_i)) != NULL)
		{
			if (fc_tbm_intersect_page(fc_a, fc_apage, fc_b))
			{
				/* 页面或块现在为空，从 a 中移除 */
				if (fc_apage->ischunk)
					fc_a->nchunks--;
				else
					fc_a->npages--;
				fc_a->nentries--;
				if (!pagetable_delete(fc_a->pagetable, fc_apage->blockno))
					elog(ERROR, "hash table corrupted");
			}
		}
	}
}

/*
 * 在交集操作期间处理 a 的一个页面
 *
 * 如果 apage 现在为空并且应该从 a 中删除，则返回 true
 */
static bool fc_tbm_intersect_page(TIDBitmap *fc_a, PagetableEntry *fc_apage, const TIDBitmap *fc_b)
{
	const PagetableEntry *fc_bpage;
	int			fc_wordnum;

	if (fc_apage->ischunk)
	{
		/* 扫描块中的每个位，尝试清除 */
		bool		fc_candelete = true;

		for (fc_wordnum = 0; fc_wordnum < WORDS_PER_CHUNK; fc_wordnum++)
		{
			bitmapword	fc_w = fc_apage->words[fc_wordnum];

			if (fc_w != 0)
			{
				bitmapword	fc_neww = fc_w;
				BlockNumber fc_pg;
				int			fc_bitnum;

				fc_pg = fc_apage->blockno + (fc_wordnum * BITS_PER_BITMAPWORD);
				fc_bitnum = 0;
				while (fc_w != 0)
				{
					if (fc_w & 1)
					{
						if (!fc_tbm_page_is_lossy(fc_b, fc_pg) &&
							fc_tbm_find_pageentry(fc_b, fc_pg) == NULL)
						{
							/* 页面根本不在 b 中，丢失损失位 */
							fc_neww &= ~((bitmapword) 1 << fc_bitnum);
						}
					}
					fc_pg++;
					fc_bitnum++;
					fc_w >>= 1;
				}
				fc_apage->words[fc_wordnum] = fc_neww;
				if (fc_neww != 0)
					fc_candelete = false;
			}
		}
		return fc_candelete;
	}
	else if (fc_tbm_page_is_lossy(fc_b, fc_apage->blockno))
	{
		/*
		 * 'a' 中的一些元组可能不满足 'b' 的要求，
		 * 但由于页面 'b' 是损失的，我们不知道哪些元组。
		 * 因此，我们将 'a' 标记为需要重新检查，以指示最多那些
		 * 设置在 'a' 中的元组是匹配的。
		 */
		fc_apage->recheck = true;
		return false;
	}
	else
	{
		bool		fc_candelete = true;

		fc_bpage = fc_tbm_find_pageentry(fc_b, fc_apage->blockno);
		if (fc_bpage != NULL)
		{
			/* 两个页面都是精确的，在位级别合并 */
			Assert(!fc_bpage->ischunk);
			for (fc_wordnum = 0; fc_wordnum < WORDS_PER_PAGE; fc_wordnum++)
			{
				fc_apage->words[fc_wordnum] &= fc_bpage->words[fc_wordnum];
				if (fc_apage->words[fc_wordnum] != 0)
					fc_candelete = false;
			}
			fc_apage->recheck |= fc_bpage->recheck;
		}
		/* 如果没有匹配的 b 页面，我们可以直接删除 a 页面 */
		return fc_candelete;
	}
}

/*
 * tbm_is_empty - TIDBitmap 是否完全为空？
 */
bool tbm_is_empty(const TIDBitmap *fc_tbm)
{
	return (fc_tbm->nentries == 0);
}

/*
 * tbm_begin_iterate - 准备遍历 TIDBitmap
 *
 * TBMIterator 结构体是在调用者的内存上下文中创建的。
 * 为了干净地结束迭代，调用 tbm_end_iterate；但也可以
 * 允许内存上下文被释放。调用者有责任在释放 TIDBitmap 后
 * 不再触碰 TBMIterator。
 *
 * 注意：一旦调用此函数，就不再允许修改位图的内容。
 * 但是，可以多次调用它以重复扫描内容，包括并行扫描。
 */
TBMIterator *
tbm_begin_iterate(TIDBitmap *fc_tbm)
{
	TBMIterator *fc_iterator;

	Assert(fc_tbm->iterating != TBM_ITERATING_SHARED);

	/*
	 * 创建 TBMIterator 结构体，留出足够的尾部空间以满足
	 * TBMIterateResult 子结构的需求。
	 */
	fc_iterator = (TBMIterator *) palloc(sizeof(TBMIterator) +
									  MAX_TUPLES_PER_PAGE * sizeof(OffsetNumber));
	fc_iterator->tbm = fc_tbm;

	/*
	 * 初始化迭代指针。
	 */
	fc_iterator->spageptr = 0;
	fc_iterator->schunkptr = 0;
	fc_iterator->schunkbit = 0;

	/*
	 * 如果我们有哈希表，创建并填充已排序的页面列表，除非
	 * 我们已经为之前的迭代器做过这件事。请注意，这些列表是
	 * 附加到位图而不是迭代器，因此可以被多个迭代器使用。
	 */
	if (fc_tbm->status == TBM_HASH && fc_tbm->iterating == TBM_NOT_ITERATING)
	{
		pagetable_iterator fc_i;
		PagetableEntry *fc_page;
		int			fc_npages;
		int			fc_nchunks;

		if (!fc_tbm->spages && fc_tbm->npages > 0)
			fc_tbm->spages = (PagetableEntry **)
				MemoryContextAlloc(fc_tbm->mcxt,
								   fc_tbm->npages * sizeof(PagetableEntry *));
		if (!fc_tbm->schunks && fc_tbm->nchunks > 0)
			fc_tbm->schunks = (PagetableEntry **)
				MemoryContextAlloc(fc_tbm->mcxt,
								   fc_tbm->nchunks * sizeof(PagetableEntry *));

		fc_npages = fc_nchunks = 0;
		pagetable_start_iterate(fc_tbm->pagetable, &fc_i);
		while ((fc_page = pagetable_iterate(fc_tbm->pagetable, &fc_i)) != NULL)
		{
			if (fc_page->ischunk)
				fc_tbm->schunks[fc_nchunks++] = fc_page;
			else
				fc_tbm->spages[fc_npages++] = fc_page;
		}
		Assert(fc_npages == fc_tbm->npages);
		Assert(fc_nchunks == fc_tbm->nchunks);
		if (fc_npages > 1)
			qsort(fc_tbm->spages, fc_npages, sizeof(PagetableEntry *),
				  fc_tbm_comparator);
		if (fc_nchunks > 1)
			qsort(fc_tbm->schunks, fc_nchunks, sizeof(PagetableEntry *),
				  fc_tbm_comparator);
	}

	fc_tbm->iterating = TBM_ITERATING_PRIVATE;

	return fc_iterator;
}

/*
 * tbm_prepare_shared_iterate - 为 TIDBitmap 准备共享迭代状态。
 *
 * 必要的共享状态将从传递给 tbm_create 的 DSA 中分配，
 * 以便多个进程可以附加到它并共同迭代。
 *
 * 这将把页表哈希转换为页面和块数组的索引
 * 进入页表数组。
 */
dsa_pointer
tbm_prepare_shared_iterate(TIDBitmap *fc_tbm)
{
	dsa_pointer fc_dp;
	TBMSharedIteratorState *fc_istate;
	PTEntryArray *fc_ptbase = NULL;
	PTIterationArray *fc_ptpages = NULL;
	PTIterationArray *fc_ptchunks = NULL;

	Assert(fc_tbm->dsa != NULL);
	Assert(fc_tbm->iterating != TBM_ITERATING_PRIVATE);

	/*
	 * 从 DSA 中分配 TBMSharedIteratorState，以保存共享成员和
	 * 锁，这也将被多个工作者用于共享迭代。
	 */
	fc_dp = dsa_allocate0(fc_tbm->dsa, sizeof(TBMSharedIteratorState));
	fc_istate = dsa_get_address(fc_tbm->dsa, fc_dp);

	/*
	 * 如果我们还未开始迭代，创建并填充已排序的页面列表。
	 * （如果我们已经在迭代，已排序的页面列表已存储在 TIDBitmap 中，
	 * 我们可以直接重用它们。）
	 */
	if (fc_tbm->iterating == TBM_NOT_ITERATING)
	{
		pagetable_iterator fc_i;
		PagetableEntry *fc_page;
		int			fc_idx;
		int			fc_npages;
		int			fc_nchunks;

		/*
		 * 从 DSA 中分配页面和块数组内存，以便在多个进程间共享。
		 */
		if (fc_tbm->npages)
		{
			fc_tbm->ptpages = dsa_allocate(fc_tbm->dsa, sizeof(PTIterationArray) +
										fc_tbm->npages * sizeof(int));
			fc_ptpages = dsa_get_address(fc_tbm->dsa, fc_tbm->ptpages);
			pg_atomic_init_u32(&fc_ptpages->refcount, 0);
		}
		if (fc_tbm->nchunks)
		{
			fc_tbm->ptchunks = dsa_allocate(fc_tbm->dsa, sizeof(PTIterationArray) +
										 fc_tbm->nchunks * sizeof(int));
			fc_ptchunks = dsa_get_address(fc_tbm->dsa, fc_tbm->ptchunks);
			pg_atomic_init_u32(&fc_ptchunks->refcount, 0);
		}

		/*
		 * 如果 TBM 状态为 TBM_HASH，则遍历页表并
		 * 将其转换为页面和块数组。但如果处于
		 * TBM_ONE_PAGE 模式，则直接从 DSA 分配一个条目的空间。
		 */
		fc_npages = fc_nchunks = 0;
		if (fc_tbm->status == TBM_HASH)
		{
			fc_ptbase = dsa_get_address(fc_tbm->dsa, fc_tbm->dsapagetable);

			pagetable_start_iterate(fc_tbm->pagetable, &fc_i);
			while ((fc_page = pagetable_iterate(fc_tbm->pagetable, &fc_i)) != NULL)
			{
				fc_idx = fc_page - fc_ptbase->ptentry;
				if (fc_page->ischunk)
					fc_ptchunks->index[fc_nchunks++] = fc_idx;
				else
					fc_ptpages->index[fc_npages++] = fc_idx;
			}

			Assert(fc_npages == fc_tbm->npages);
			Assert(fc_nchunks == fc_tbm->nchunks);
		}
		else if (fc_tbm->status == TBM_ONE_PAGE)
		{
			/*
			 * 在单页面模式下，为一个页表条目分配空间，
			 * 初始化它，并直接将其索引（即 0）存储在
			 * 页面数组中。
			 */
			fc_tbm->dsapagetable = dsa_allocate(fc_tbm->dsa, sizeof(PTEntryArray) +
											 sizeof(PagetableEntry));
			fc_ptbase = dsa_get_address(fc_tbm->dsa, fc_tbm->dsapagetable);
			memcpy(fc_ptbase->ptentry, &fc_tbm->entry1, sizeof(PagetableEntry));
			fc_ptpages->index[0] = 0;
		}

		if (fc_ptbase != NULL)
			pg_atomic_init_u32(&fc_ptbase->refcount, 0);
		if (fc_npages > 1)
			qsort_arg((void *) (fc_ptpages->index), fc_npages, sizeof(int),
					  fc_tbm_shared_comparator, (void *) fc_ptbase->ptentry);
		if (fc_nchunks > 1)
			qsort_arg((void *) (fc_ptchunks->index), fc_nchunks, sizeof(int),
					  fc_tbm_shared_comparator, (void *) fc_ptbase->ptentry);
	}

	/*
	 * 将 TBM 成员存储在共享状态中，以便我们可以在多个进程
	 * 之间共享它们。
	 */
	fc_istate->nentries = fc_tbm->nentries;
	fc_istate->maxentries = fc_tbm->maxentries;
	fc_istate->npages = fc_tbm->npages;
	fc_istate->nchunks = fc_tbm->nchunks;
	fc_istate->pagetable = fc_tbm->dsapagetable;
	fc_istate->spages = fc_tbm->ptpages;
	fc_istate->schunks = fc_tbm->ptchunks;

	fc_ptbase = dsa_get_address(fc_tbm->dsa, fc_tbm->dsapagetable);
	fc_ptpages = dsa_get_address(fc_tbm->dsa, fc_tbm->ptpages);
	fc_ptchunks = dsa_get_address(fc_tbm->dsa, fc_tbm->ptchunks);

	/*
	 * 对于每个共享迭代器，参考页表和迭代器数组，
	 * 将引用计数增加 1，以便在释放共享迭代器时
	 * 不会释放页表和迭代器数组，直到其引用计数变为 0。
	 */
	if (fc_ptbase != NULL)
		pg_atomic_add_fetch_u32(&fc_ptbase->refcount, 1);
	if (fc_ptpages != NULL)
		pg_atomic_add_fetch_u32(&fc_ptpages->refcount, 1);
	if (fc_ptchunks != NULL)
		pg_atomic_add_fetch_u32(&fc_ptchunks->refcount, 1);

	/* 初始化迭代器锁 */
	LWLockInitialize(&fc_istate->lock, LWTRANCHE_SHARED_TIDBITMAP);

	/* 初始化共享迭代器状态 */
	fc_istate->schunkbit = 0;
	fc_istate->schunkptr = 0;
	fc_istate->spageptr = 0;

	fc_tbm->iterating = TBM_ITERATING_SHARED;

	return fc_dp;
}

/*
 * tbm_extract_page_tuple - 从页面提取元组偏移量
 *
 * 提取的偏移量存储到 TBMIterateResult 中。
 */
static inline int fc_tbm_extract_page_tuple(PagetableEntry *fc_page, TBMIterateResult *fc_output)
{
	int			fc_wordnum;
	int			fc_ntuples = 0;

	for (fc_wordnum = 0; fc_wordnum < WORDS_PER_PAGE; fc_wordnum++)
	{
		bitmapword	fc_w = fc_page->words[fc_wordnum];

		if (fc_w != 0)
		{
			int			fc_off = fc_wordnum * BITS_PER_BITMAPWORD + 1;

			while (fc_w != 0)
			{
				if (fc_w & 1)
					fc_output->offsets[fc_ntuples++] = (OffsetNumber) fc_off;
				fc_off++;
				fc_w >>= 1;
			}
		}
	}

	return fc_ntuples;
}

/*
 *	tbm_advance_schunkbit - 前进 schunkbit
 */
static inline void fc_tbm_advance_schunkbit(PagetableEntry *fc_chunk, int *fc_schunkbitp)
{
	int			fc_schunkbit = *fc_schunkbitp;

	while (fc_schunkbit < PAGES_PER_CHUNK)
	{
		int			fc_wordnum = WORDNUM(fc_schunkbit);
		int			fc_bitnum = BITNUM(fc_schunkbit);

		if ((fc_chunk->words[fc_wordnum] & ((bitmapword) 1 << fc_bitnum)) != 0)
			break;
		fc_schunkbit++;
	}

	*fc_schunkbitp = fc_schunkbit;
}

/*
 * tbm_iterate - 扫描 TIDBitmap 的下一页
 *
 * 返回表示一页的 TBMIterateResult，如果没有更多页面可扫描，则返回 NULL。
 * 页面确保按数字顺序交付。如果 result->ntuples < 0，则位图是
 * "不精确的"，未能记住此页面上要查看的确切元组 ---
 * 调用者必须检查页面上的所有元组并检查它们是否符合
 * 预期条件。如果 result->recheck 为 true，只有指示的元组需要
 * 被检查，但条件仍必须重新检查。（为了测试方便，当 ntuples < 0 时，
 * 重新检查始终设置为 true。）
 */
TBMIterateResult *
tbm_iterate(TBMIterator *fc_iterator)
{
	TIDBitmap  *fc_tbm = fc_iterator->tbm;
	TBMIterateResult *fc_output = &(fc_iterator->output);

	Assert(fc_tbm->iterating == TBM_ITERATING_PRIVATE);

	/*
	 * 如果存在不精确的块页面，确保我们已将 schunkptr/
	 * schunkbit 前进到下一个设置位。
	 */
	while (fc_iterator->schunkptr < fc_tbm->nchunks)
	{
		PagetableEntry *fc_chunk = fc_tbm->schunks[fc_iterator->schunkptr];
		int			fc_schunkbit = fc_iterator->schunkbit;

		fc_tbm_advance_schunkbit(fc_chunk, &fc_schunkbit);
		if (fc_schunkbit < PAGES_PER_CHUNK)
		{
			fc_iterator->schunkbit = fc_schunkbit;
			break;
		}
		/* 前进到下一个块 */
		fc_iterator->schunkptr++;
		fc_iterator->schunkbit = 0;
	}

	/*
	 * 如果块和每页面数据都剩余，必须输出数字上较早的页面。
	 */
	if (fc_iterator->schunkptr < fc_tbm->nchunks)
	{
		PagetableEntry *fc_chunk = fc_tbm->schunks[fc_iterator->schunkptr];
		BlockNumber fc_chunk_blockno;

		fc_chunk_blockno = fc_chunk->blockno + fc_iterator->schunkbit;
		if (fc_iterator->spageptr >= fc_tbm->npages ||
			fc_chunk_blockno < fc_tbm->spages[fc_iterator->spageptr]->blockno)
		{
			/* 从块中返回不精确页面指示符 */
			fc_output->blockno = fc_chunk_blockno;
			fc_output->ntuples = -1;
			fc_output->recheck = true;
			fc_iterator->schunkbit++;
			return fc_output;
		}
	}

	if (fc_iterator->spageptr < fc_tbm->npages)
	{
		PagetableEntry *fc_page;
		int			fc_ntuples;

		/* 在 TBM_ONE_PAGE 状态下，我们不分配 spages[] 数组 */
		if (fc_tbm->status == TBM_ONE_PAGE)
			fc_page = &fc_tbm->entry1;
		else
			fc_page = fc_tbm->spages[fc_iterator->spageptr];

		/* 扫描位图以提取各个偏移量 */
		fc_ntuples = fc_tbm_extract_page_tuple(fc_page, fc_output);
		fc_output->blockno = fc_page->blockno;
		fc_output->ntuples = fc_ntuples;
		fc_output->recheck = fc_page->recheck;
		fc_iterator->spageptr++;
		return fc_output;
	}

	/* 位图中没有更多内容 */
	return NULL;
}

/*
 *	tbm_shared_iterate - 扫描 TIDBitmap 的下一页
 *
 *	如上所述，但这将使用一个在多个进程之间共享的迭代器进行迭代。
 *	在访问共享成员之前，我们需要获取迭代器 LWLock。
 */
TBMIterateResult *
tbm_shared_iterate(TBMSharedIterator *fc_iterator)
{
	TBMIterateResult *fc_output = &fc_iterator->output;
	TBMSharedIteratorState *fc_istate = fc_iterator->state;
	PagetableEntry *fc_ptbase = NULL;
	int		   *fc_idxpages = NULL;
	int		   *fc_idxchunks = NULL;

	if (fc_iterator->ptbase != NULL)
		fc_ptbase = fc_iterator->ptbase->ptentry;
	if (fc_iterator->ptpages != NULL)
		fc_idxpages = fc_iterator->ptpages->index;
	if (fc_iterator->ptchunks != NULL)
		fc_idxchunks = fc_iterator->ptchunks->index;

	/* 在访问共享成员之前获取 LWLock */
	LWLockAcquire(&fc_istate->lock, LW_EXCLUSIVE);

	/*
	 * 如果存在不精确的块页面，确保我们已将 schunkptr/
	 * schunkbit 前进到下一个设置位。
	 */
	while (fc_istate->schunkptr < fc_istate->nchunks)
	{
		PagetableEntry *fc_chunk = &fc_ptbase[fc_idxchunks[fc_istate->schunkptr]];
		int			fc_schunkbit = fc_istate->schunkbit;

		fc_tbm_advance_schunkbit(fc_chunk, &fc_schunkbit);
		if (fc_schunkbit < PAGES_PER_CHUNK)
		{
			fc_istate->schunkbit = fc_schunkbit;
			break;
		}
		/* 前进到下一个块 */
		fc_istate->schunkptr++;
		fc_istate->schunkbit = 0;
	}

	/*
	 * 如果块和每页面数据都剩余，必须输出数字上较早的页面。
	 */
	if (fc_istate->schunkptr < fc_istate->nchunks)
	{
		PagetableEntry *fc_chunk = &fc_ptbase[fc_idxchunks[fc_istate->schunkptr]];
		BlockNumber fc_chunk_blockno;

		fc_chunk_blockno = fc_chunk->blockno + fc_istate->schunkbit;

		if (fc_istate->spageptr >= fc_istate->npages ||
			fc_chunk_blockno < fc_ptbase[fc_idxpages[fc_istate->spageptr]].blockno)
		{
			/* 从块中返回不精确页面指示符 */
			fc_output->blockno = fc_chunk_blockno;
			fc_output->ntuples = -1;
			fc_output->recheck = true;
			fc_istate->schunkbit++;

			LWLockRelease(&fc_istate->lock);
			return fc_output;
		}
	}

	if (fc_istate->spageptr < fc_istate->npages)
	{
		PagetableEntry *fc_page = &fc_ptbase[fc_idxpages[fc_istate->spageptr]];
		int			fc_ntuples;

		/* 扫描位图以提取各个偏移量 */
		fc_ntuples = fc_tbm_extract_page_tuple(fc_page, fc_output);
		fc_output->blockno = fc_page->blockno;
		fc_output->ntuples = fc_ntuples;
		fc_output->recheck = fc_page->recheck;
		fc_istate->spageptr++;

		LWLockRelease(&fc_istate->lock);

		return fc_output;
	}

	LWLockRelease(&fc_istate->lock);

	/* 位图中没有更多内容 */
	return NULL;
}

/*
 * tbm_end_iterate - 完成对 TIDBitmap 的迭代
 *
 * 当前这只是 pfree，但将来可能会做更多事情。
 * （例如，计算打开的迭代器并允许位图在没有更多迭代器时返回
 * 读/写状态可能会有用。）
 */
void tbm_end_iterate(TBMIterator *fc_iterator)
{
	pfree(fc_iterator);
}

/*
 * tbm_end_shared_iterate - 完成对 TIDBitmap 的共享迭代
 *
 * 这不会释放与迭代器相关联的任何共享状态，
 * 仅释放我们后端私有状态。
 */
void tbm_end_shared_iterate(TBMSharedIterator *fc_iterator)
{
	pfree(fc_iterator);
}


/*******************************
 * tbm_find_pageentry - 查找指定页码的 PagetableEntry
 *
 * 如果该页码没有非损失性条目，则返回 NULL。
 */
static const PagetableEntry *
fc_tbm_find_pageentry(const TIDBitmap *fc_tbm, BlockNumber fc_pageno)
{
	const PagetableEntry *fc_page;

	if (fc_tbm->nentries == 0)		/* 如果页表不存在 */ 
		return NULL;

	if (fc_tbm->status == TBM_ONE_PAGE)
	{
		fc_page = &fc_tbm->entry1;
		if (fc_page->blockno != fc_pageno)
			return NULL;
		Assert(!fc_page->ischunk);
		return fc_page;
	}

	fc_page = pagetable_lookup(fc_tbm->pagetable, fc_pageno);
	if (fc_page == NULL)
		return NULL;
	if (fc_page->ischunk)
		return NULL;			/* 不想要一个有损的区块头 */
	return fc_page;
}

/*
 * tbm_get_pageentry - 查找或创建一个与页面编号对应的 PagetableEntry
 *
 * 如果是新的，则该条目被标记为确切（非区块）条目。
 *
 * 这可能导致表超出所需的内存大小。调用者需要在下一个安全点调用 tbm_lossify()。
 */
static PagetableEntry *
fc_tbm_get_pageentry(TIDBitmap *fc_tbm, BlockNumber fc_pageno)
{
	PagetableEntry *fc_page;
	bool		fc_found;

	if (fc_tbm->status == TBM_EMPTY)
	{
		/* 使用固定插槽 */
		fc_page = &fc_tbm->entry1;
		fc_found = false;
		fc_tbm->status = TBM_ONE_PAGE;
	}
	else
	{
		if (fc_tbm->status == TBM_ONE_PAGE)
		{
			fc_page = &fc_tbm->entry1;
			if (fc_page->blockno == fc_pageno)
				return fc_page;
			/* 该切换时机是从一个页面到哈希表 */
			fc_tbm_create_pagetable(fc_tbm);
		}

		/* 查找或创建一个条目 */
		fc_page = pagetable_insert(fc_tbm->pagetable, fc_pageno, &fc_found);
	}

	/* 如果之前不存在则初始化它 */
	if (!fc_found)
	{
		char		fc_oldstatus = fc_page->status;

		MemSet(fc_page, 0, sizeof(PagetableEntry));
		fc_page->status = fc_oldstatus;
		fc_page->blockno = fc_pageno;
		/* 也必须计算它 */
		fc_tbm->nentries++;
		fc_tbm->npages++;
	}

	return fc_page;
}

/*
 * tbm_page_is_lossy - 页面是否标记为有损存储？
 */
static bool fc_tbm_page_is_lossy(const TIDBitmap *fc_tbm, BlockNumber fc_pageno)
{
	PagetableEntry *fc_page;
	BlockNumber fc_chunk_pageno;
	int			fc_bitno;

	/* 如果没有有损的区块，我们可以跳过查找 */
	if (fc_tbm->nchunks == 0)
		return false;
	Assert(fc_tbm->status == TBM_HASH);

	fc_bitno = fc_pageno % PAGES_PER_CHUNK;
	fc_chunk_pageno = fc_pageno - fc_bitno;

	fc_page = pagetable_lookup(fc_tbm->pagetable, fc_chunk_pageno);

	if (fc_page != NULL && fc_page->ischunk)
	{
		int			fc_wordnum = WORDNUM(fc_bitno);
		int			fc_bitnum = BITNUM(fc_bitno);

		if ((fc_page->words[fc_wordnum] & ((bitmapword) 1 << fc_bitnum)) != 0)
			return true;
	}
	return false;
}

/*
 * tbm_mark_page_lossy - 将页面编号标记为有损存储
 *
 * 这可能导致表超出所需的内存大小。调用者需要在下一个安全点调用 tbm_lossify()。
 */
static void fc_tbm_mark_page_lossy(TIDBitmap *fc_tbm, BlockNumber fc_pageno)
{
	PagetableEntry *fc_page;
	bool		fc_found;
	BlockNumber fc_chunk_pageno;
	int			fc_bitno;
	int			fc_wordnum;
	int			fc_bitnum;

	/* 每当它是有损的，我们强制位图进入哈希表模式 */
	if (fc_tbm->status != TBM_HASH)
		fc_tbm_create_pagetable(fc_tbm);

	fc_bitno = fc_pageno % PAGES_PER_CHUNK;
	fc_chunk_pageno = fc_pageno - fc_bitno;

	/*
	 * 删除页面的任何现存非有损条目。然而，如果该页面是其自身的
	 * 区块头，则我们跳过此操作并在下面处理这种情况。
	 */
	if (fc_bitno != 0)
	{
		if (pagetable_delete(fc_tbm->pagetable, fc_pageno))
		{
			/* 它是存在的，所以调整计数 */
			fc_tbm->nentries--;
			fc_tbm->npages--;		/* 假设它必须是非有损的 */
		}
	}

	/* 查找或创建区块头页面的条目 */
	fc_page = pagetable_insert(fc_tbm->pagetable, fc_chunk_pageno, &fc_found);

	/* 如果之前不存在则初始化它 */
	if (!fc_found)
	{
		char		fc_oldstatus = fc_page->status;

		MemSet(fc_page, 0, sizeof(PagetableEntry));
		fc_page->status = fc_oldstatus;
		fc_page->blockno = fc_chunk_pageno;
		fc_page->ischunk = true;
		/* 也必须计算它 */
		fc_tbm->nentries++;
		fc_tbm->nchunks++;
	}
	else if (!fc_page->ischunk)
	{
		char		fc_oldstatus = fc_page->status;

		/* 区块头页面以前是非有损的，标记为有损 */
		MemSet(fc_page, 0, sizeof(PagetableEntry));
		fc_page->status = fc_oldstatus;
		fc_page->blockno = fc_chunk_pageno;
		fc_page->ischunk = true;
		/* 我们假设它至少有一些元组位设置，所以标记为有损 */
		fc_page->words[0] = ((bitmapword) 1 << 0);
		/* 调整计数 */
		fc_tbm->nchunks++;
		fc_tbm->npages--;
	}

	/* 现在设置原始目标页面的位 */
	fc_wordnum = WORDNUM(fc_bitno);
	fc_bitnum = BITNUM(fc_bitno);
	fc_page->words[fc_wordnum] |= ((bitmapword) 1 << fc_bitnum);
}

/*
 * tbm_lossify - 失去一些信息以使内存限制不超标
 */
static void fc_tbm_lossify(TIDBitmap *fc_tbm)
{
	pagetable_iterator fc_i;
	PagetableEntry *fc_page;

	/*
	 * XXX 真的很愚蠢的实现：这仅仅是以基本随机顺序使页面有损。
	 * 我们应该更多地关注每个页面中设置的位数。
	 *
	 * 由于我们在 nentries 超过 maxentries 时立即被调用，我们应该
	 * 将 nentries 压降到显著低于 maxentries，否则我们很快会再次
	 * 遇到这种情况。我们的目标是 maxentries/2。
	 */
	Assert(fc_tbm->iterating == TBM_NOT_ITERATING);
	Assert(fc_tbm->status == TBM_HASH);

	pagetable_start_iterate_at(fc_tbm->pagetable, &fc_i, fc_tbm->lossify_start);
	while ((fc_page = pagetable_iterate(fc_tbm->pagetable, &fc_i)) != NULL)
	{
		if (fc_page->ischunk)
			continue;			/* 已经是区块头 */

		/*
		 * 如果该页面会变成区块头，转换为有损存储就不会保存任何东西，
		 * 所以跳过它。
		 */
		if ((fc_page->blockno % PAGES_PER_CHUNK) == 0)
			continue;

		/* 这完成了艰巨的工作... */
		fc_tbm_mark_page_lossy(fc_tbm, fc_page->blockno);

		if (fc_tbm->nentries <= fc_tbm->maxentries / 2)
		{
			/*
			 * 我们已经腾出了足够的空间。记住下一轮开始有损存储的位置，
			 * 以便我们均匀地遍历哈希表。
			 */
			fc_tbm->lossify_start = fc_i.cur;
			break;
		}

		/*
		 * 注意：tbm_mark_page_lossy 可能已经将一个有损区块插入哈希表并
		 * 删除了非有损区块。我们可以继续同样的哈希表扫描，因为
		 * 漏掉一个元素或访问新插入的元素并不致命。
		 */
	}

	/*
	 * 对于一个大的位图和小的 work_mem，可能无法降到 maxentries 之下。
	 * 如果发生这种情况，我们将无谓地不断调用 tbm_lossify。
	 * 为了防止这种情况影响性能，强制将 maxentries 提高到至少是当前
	 * 条目的两倍。（本质上，我们承认在执行此操作时无法在 work_mem 内
	 * 部放下。）请注意，如果我们提前跳出了循环，则该测试不会触发；
	 * 如果没有，当前的条目数显然是无法进一步减少的。
	 */
	if (fc_tbm->nentries > fc_tbm->maxentries / 2)
		fc_tbm->maxentries = Min(fc_tbm->nentries, (INT_MAX - 1) / 2) * 2;
}

/*
 * qsort 比较器以处理 PagetableEntry 指针。
 */
static int fc_tbm_comparator(const void *fc_left, const void *fc_right)
{
	BlockNumber fc_l = (*((PagetableEntry *const *) fc_left))->blockno;
	BlockNumber fc_r = (*((PagetableEntry *const *) fc_right))->blockno;

	if (fc_l < fc_r)
		return -1;
	else if (fc_l > fc_r)
		return 1;
	return 0;
}

/*
 * 与上面相同，但这将索引 PagetableEntry 数组。因此，
 * 在比较 blockno 之前，需要获取实际的 PagetableEntry。
 */
static int fc_tbm_shared_comparator(const void *fc_left, const void *fc_right, void *fc_arg)
{
	PagetableEntry *fc_base = (PagetableEntry *) fc_arg;
	PagetableEntry *fc_lpage = &fc_base[*(int *) fc_left];
	PagetableEntry *fc_rpage = &fc_base[*(int *) fc_right];

	if (fc_lpage->blockno < fc_rpage->blockno)
		return -1;
	else if (fc_lpage->blockno > fc_rpage->blockno)
		return 1;
	return 0;
}

/*
 *	tbm_attach_shared_iterate
 *
 *	 分配一个后端私有迭代器并将共享迭代器状态附加到它，
 *	 以便多个处理可以共同迭代。
 *
 *	 我们还将 DSA 指针转换为本地指针并将它们存储到
 *	 我们的私有迭代器中。
 */
TBMSharedIterator *
tbm_attach_shared_iterate(dsa_area *fc_dsa, dsa_pointer fc_dp)
{
	TBMSharedIterator *fc_iterator;
	TBMSharedIteratorState *fc_istate;

	/*
	 * 创建 TBMSharedIterator 结构体，保留足够的尾部空间以
	 * 满足 TBMIterateResult 子结构的需求。
	 */
	fc_iterator = (TBMSharedIterator *) palloc0(sizeof(TBMSharedIterator) +
											 MAX_TUPLES_PER_PAGE * sizeof(OffsetNumber));

	fc_istate = (TBMSharedIteratorState *) dsa_get_address(fc_dsa, fc_dp);

	fc_iterator->state = fc_istate;

	fc_iterator->ptbase = dsa_get_address(fc_dsa, fc_istate->pagetable);

	if (fc_istate->npages)
		fc_iterator->ptpages = dsa_get_address(fc_dsa, fc_istate->spages);
	if (fc_istate->nchunks)
		fc_iterator->ptchunks = dsa_get_address(fc_dsa, fc_istate->schunks);

	return fc_iterator;
}

/*
 * pagetable_allocate
 *
 * 为哈希表元素分配内存的回调函数。
 * 使用 DSA（如果可用）为哈希表元素分配内存。
 */
static inline void *
pagetable_allocate(pagetable_hash *pagetable, Size size)
{
	TIDBitmap  *tbm = (TIDBitmap *) pagetable->private_data;
	PTEntryArray *ptbase;

	if (tbm->dsa == NULL)
		return MemoryContextAllocExtended(pagetable->ctx, size,
										  MCXT_ALLOC_HUGE | MCXT_ALLOC_ZERO);

	/*
	 * 在分配新内存之前，将 dsapagetable 引用保存到 dsapagetableold，
	 * 以便 pagetable_free 可以释放旧条目。
	 */
	tbm->dsapagetableold = tbm->dsapagetable;
	tbm->dsapagetable = dsa_allocate_extended(tbm->dsa,
											  sizeof(PTEntryArray) + size,
											  DSA_ALLOC_HUGE | DSA_ALLOC_ZERO);
	ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);

	return ptbase->ptentry;
}

/*
 * pagetable_free
 *
 * 释放哈希表元素的回调函数。
 */
static inline void pagetable_free(pagetable_hash *pagetable, void *pointer)
{
	TIDBitmap  *tbm = (TIDBitmap *) pagetable->private_data;

	/* 如果 DSA 不可用，则释放输入指针 */
	if (tbm->dsa == NULL)
		pfree(pointer);
	else if (DsaPointerIsValid(tbm->dsapagetableold))
	{
		dsa_free(tbm->dsa, tbm->dsapagetableold);
		tbm->dsapagetableold = InvalidDsaPointer;
	}
}

/*
 * tbm_calculate_entries
 *
 * 估算在 maxbytes 内可以拥有的哈希表条目数。
 */
long tbm_calculate_entries(double fc_maxbytes)
{
	long		fc_nbuckets;

	/*
	 * 估算在 maxbytes 内可以拥有的哈希表条目数。此
	 * 估算哈希成本为 sizeof(PagetableEntry)，这对于我们的目的
	 * 是足够的。还要为在迭代读出过程中创建的数组每个条目
	 * 计算一个额外的指针。
	 */
	fc_nbuckets = fc_maxbytes /
		(sizeof(PagetableEntry) + sizeof(Pointer) + sizeof(Pointer));
	fc_nbuckets = Min(fc_nbuckets, INT_MAX - 1);	/* 安全限制 */
	fc_nbuckets = Max(fc_nbuckets, 16);	/* 理智限制 */

	return fc_nbuckets;
}
